package com.tgy.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: tgy
 * @Date: 12/1/20 10:20 AM
 *
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 */
public class _239_滑动窗口最大值 {

    public int[] maxSlidingWindow(int[] nums, int k) {

        if (nums == null || k <= 0 || nums.length < k) {

            return new int[0];
        }

        if (k == 1) {

            return nums;
        }

        int[] ret = new int[nums.length - k + 1];

        /**
         * 双端队列里面存放的是索引，不是数组里面的值
         */
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {

            int val = nums[i];

            while (!deque.isEmpty() && val >= nums[deque.peekLast()]) {

                deque.pollLast();
            }

            deque.offerLast(i);
            int left = i - k + 1;
            if (left < 0) {

                continue;
            }

            if (deque.peekFirst() < left) {

                deque.pollFirst();
            }

            ret[left] = nums[deque.peekFirst()];
        }

        return ret;
    }
}
